For the design of an integrated circuit or a structure in semiconductor technology (generally termed “layout”) the verification of each element within a layout against design rules is of great importance. The design rules define the conditions that are, for example, necessary for a successful manufacturing of semiconductor devices. Basic definitions of the terms used in the following description are found, for example, in U.S. Pat. No. 5,528,508, which is incorporated herein by reference.
In the layout of integrated circuits or the layout of other structures of semiconductor devices the design rule checks (DRC) or similar operations can be divided into two classes:
1. Local operations: The results can be computed by taking local interactions between shapes into account. Shapes in this context are understood to be geometric forms representing structures or a part of a structure in the layout. Shapes in particular can be geometric primitives such as boxes, wires or polygons.
A local interaction here means that the interaction is limited by the range (distance). Examples of such local operations are: Geometric operations as Boolean Operators (AND, ANDNOT, XOR), spacing checks and distance checks or the placing of elements for an Optical Proximity Correction (OPC). An example for a spacing check would be, for example, that a rule requires that the space between two metal edges is not below a certain value; otherwise a short circuit might occur.
2. Non-local Operations: The results can be computed by taking into account closed regions (also termed as groups) of interacting shapes. The determination of the area of hierarchically distributed mask polygons is an example for such a non-local operation.
Layout data for a design is commonly structured in a hierarchy of cells since such a structure in general is computationally easier to handle than a flat structure. Each cell in this context may contain shapes, i.e., geometric forms forming the structure of the actual layout, or other cells referred to as subcells or child cells. The cell containing the subcell is then also referred to as parent cell to the subcell.
One cell may occur several times in a layout, the occurrences of the cell in the layout being referred to as instances of the cell.
In a flat design rule checking tool, each subcell of a layout is replaced by a copy of the referenced cell to produce a flat layout containing only shapes, i.e., geometric forms. The resulting data structure is large and, therefore, can be handled only in a computationally expensive manner.
A hierarchical design rule checking tool on the other hand performs the design rule check directly on the hierarchical data structure of the layout. This allows a computationally efficient handling, but design rule check tools are more complicated to implement.
Hierarchical, physical verification tools of layouts (e.g., Assura by Cadence and Calibre by Mentor Graphics) differ in their computational time, the data volume for intermediate results and end results and in the representation of the results in the cell hierarchy. This influences the assessment of the results by the layout designers. The methods used for the processing of the hierarchy herein have a decisive influence on the mentioned aspects, i.e., the computation time and the data volume to be kept in storage.
An inefficient hierarchy processing may, for example, lead to longer design times for a DRC in the layout design or for simulation based OPC.
From the following references, each of which is incorporated herein by reference, it is known to use methods involving “Inverse Layout Trees,” (ILT) to collect and process the hierarchical shape and cell interactions for a layout and to represent the results in a layout hierarchy:
Hedenstierna, Jeppson, “The use of inverse layout trees of hierarchial design rule checking,” 26th ACM/IEEE Design Automation Conference, 1989.
Hedenstierna, Jeppson, “The use of inverse layout trees for hierarchical design verification,” Proceedings of ICCAD-88, Santa Clara, pp. 534-537, November 1988.
Hedenstierna, Jeppson, “The Halo Algorithm—An algorithm for hierarchical design rule checking of VLSI circuits,” IEEE Transactions of Computer Aided Design of Integrated Circuits and System, Vol. 12, No. 2, February 1993.
U.S. Pat. No. 5,528,508 discloses a method that additionally uses a counter for instances for that purpose.
U.S. Pat. No. 5,559,718 describes a method in which a processing unit is coupled to a verification database. The result register has an input and an output, whereby the input of the result register is coupled to the output of a processing unit. The processing unit can override individual results.